1. Field of the Invention
The present invention relates to databases, and more particularly to indexes associated with databases.
2. Background Art
Database systems generally provide indexes to increase the speed of the data retrieval process. A database index is conceptually similar to an index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied with a location of the information. Values in one or more columns of a table are stored in an index, which is typically maintained separately from the actual database table (or the underlying base table). The ordered list of information in an index allows for quick scanning to find a target value or range of values. Moreover, since a conventional index stores only the values from one or more columns that serve as the key to the index, a pointer and a unique row identifier if necessary, the number of blocks of data being read into memory is significantly reduced as compared to a fall table scan which would be a needed if an index were not used.
To save storage space needed to store an index and to reduce the amount of data transfer involved in query processing, different compression techniques may be used to compress indexes. Different types of index compression techniques include techniques that employ variable length coding or fixed-length index key compression. Although these compression techniques may help in conserving some disk space, they require separate phases of compression and decompression. As a consequence, for improved cache utilization and faster disk-to-memory transfer, decompression speeds must be high. Furthermore, since separate compression and decompression phases require re-writing of an index, existing index compression methods become computationally intensive.
Therefore, what is needed is a system, method and computer program product that compresses indexes in a manner that overcomes limitations of existing index compression techniques.